 package elementaryAlgorithm;

 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Queue;
 import java.util.Set;

 /**
 * @author 郭辉
 * @className TODO
 * @description 433. 最小基因变化
 * 基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
 *
 * 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
 *
 * 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
 * 另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必 21须位于基因库 bank 中）
 *
 * 给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
 *
 * 注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
 *
 *
 *
 * 示例 1：
 *
 * 输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
 * 输出：1
 * 示例 2：
 *
 * 输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
 * 输出：2
 * 示例 3：
 *
 * 输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
 * 输出：3
 *
 *
 * 提示：
 *
 * start.length == 8
 * end.length == 8
 * 0 <= bank.length <= 10
 * bank[i].length == 8
 * start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成
 * 通过次数50,318提交次数91,560
 * @date 2023/4/7 10:17
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet433 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        if (!Arrays.asList(bank).contains(endGene) || bank == null || bank.length == 0){
            return -1;
        }
        return bfs(startGene,endGene, Arrays.asList(bank));
    }
    
    public int bfs(String start, String end, List<String> bank){
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.add(start);
        visited.add(start);
        int step = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String poll = queue.poll();

                if (poll.equals(end)){
                    return step;
                }
                if (!bank.contains(poll) && poll != start){
                    continue;
                }
                for (int j = 0; j < 8; j++) {
                    for (int k = 0; k < 4; k++) {
                        String change = change(poll, j,k);
                        if (!visited.contains(change) && bank.contains(change)){
                            queue.add(change);
                            visited.add(change);
                        }
                    }
                }
            }
            step++;
        }

        return -1;
    }

    public String change(String pamram,int index,int k){
        char[] chars = pamram.toCharArray();
        if (k == 0){
            chars[index] = 'A';
        }
        if (k == 1){
            chars[index] = 'C';
        }
        if (k == 2){
            chars[index] = 'G';
        }
        if (k == 3){
            chars[index] = 'T';
        }
        return new String(chars);
    }

     public static void main(String[] args) {
         Leet433 leet433 = new Leet433();
         String start = "AAAAACCC", end = "AACCCCCC";
         String[] bank = {"AAAACCCC","AAACCCCC","AACCCCCC"};
         System.out.println(leet433.minMutation(start, end, bank));
     }
}
